1. Field of the Invention
The present invention generally relates to decision rules for data mining and, more particularly, to a method that generates Disjunctive Normal Form (DNF) rules using lightweight rule induction. The induction method attempts to minimize classification error.
2. Background Description
Decision trees and decision rules are well-known and related types of classifiers. The terminal nodes of a tree can be grouped into Disjunctive Normal Form (DNF) rules, only one of which is satisfied for a new case. Decision rules are also DNF rules, but allow rules to overlap, which potentially allows for more compact and interesting rule sets.
Decision tree induction methods are more efficient than those for decision rule inductionxe2x80x94some methods for decision rule induction actually start with an induced decision tree. Procedures for pruning and optimization are relatively complex (see S. Weiss and N. Indurkhya, xe2x80x9cOptimized Rule Induction,xe2x80x9d IEEE EXPERT, 8(6), pp. 61-69 (1993); and W. Cohen, xe2x80x9cFast Effective Rule Induction,xe2x80x9d The XII International Conference on Machine Learning, pp. 115-123 (1995)). In terms of predictive performance, logic-based methods have difficulty with applications having complex solutions. With lesser support for many of the rules, the induced solutions are often bedeviled by high variance, where the training error is far from the test error.
Single decision trees are often dramatically outperformed by voting methods for multiple decision trees. Such methods produce exaggeratedly complex solutions, but they may be the best obtainable with any classifier. In W. Cohen and Y. Singer, xe2x80x9cA Simple, Fast, and Effective Rule Learner,xe2x80x9d Proceedings of Annual Conference of American Association for Artificial Intelligence, pp. 335-342 (1999), boosting techniques, as described in R. Schapire, xe2x80x9cA Brief Introduction to Boosting,xe2x80x9d Proceedings of International Joint Conference on Artificial Intelligence, pp. 1401-1405 (1999), are used by a system called SLIPPER to generate a weighted set of rules that are shown to generally outperform standard rule induction techniques. While these rules can maintain clarity of explanation, they do not match the predictive performance of the strongest learning methods, such as boosted trees. Of particular interest to the present invention is J. Friedman, T. Hastie and R. Tibshirani, xe2x80x9cAdditive Logistic Regression: A Statistical View of Boosting,xe2x80x9d Technical Report, Stanford University Statistics Department (1998) where very small trees are boosted to high predictive performance by truncated tree induction (TTI). Small trees can be decomposed into a collection of interpretable rules. Some of the boosted collections of tiny trees, even tree stumps, have actually performed best on benchmark applications.
It is therefore an object of the invention to provide a lightweight rule induction method that generates compact Disjunctive Normal Form (DNF) rules.
According to the invention, each class may have an equal number of unweighted rules. A new example is classified by applying all rules and assigning the example to the class with the most satisfied rules. The induction method attempts to minimize the training error with no pruning. An overall design is specified by setting limits on the size and number of rules. During training, cases are adaptively weighted using a simple cumulative error method. The induction method is nearly linear in time relative to an increase in the number of induced rules or the number of cases. Experimental results on large benchmark datasets demonstrate that predictive performance can rival the best reported results in the literature.